1. Field of the Invention
The present invention generally relates to the fabrication and design of semiconductor chips and integrated circuits, and more particularly to the physical layout (placement) of logic cells in an integrated circuit design.
2. Description of the Related Art
Integrated circuits are used for a wide variety of electronic applications, from simple devices such as wristwatches to the most complex computer systems. A microelectronic integrated circuit (IC) chip can generally be thought of as a collection of logic cells with electrical interconnections between the cells, formed on a semiconductor substrate (e.g., silicon). An IC may include a very large number of cells and require complicated connections between the cells. A cell (or module) is a group of one or more circuit elements such as transistors, capacitors, resistors, inductors, and other basic circuit elements grouped to perform a logic function. Cell types include, for example, core cells, scan cells and input/output (I/O) cells. Each of the cells of an IC may have one or more pins, each of which in turn may be connected to one or more other pins of the IC by wires. The wires connecting the pins of the IC are also formed on the surface of the chip. For more complex designs, there are typically at least four distinct layers of conducting media available for routing, such as a polysilicon layer and three metal layers (metal-1, metal-2, and metal-3). The polysilicon layer, metal-1, metal-2, and metal-3 are all used for vertical and/or horizontal routing.
An IC chip is fabricated by first conceiving the logical circuit description, and then converting that logical description into a physical description, or geometric layout. This process is usually carried out using a “netlist,” which is a record of all of the nets, or interconnections, between the cell pins. A layout typically consists of a set of planar geometric shapes in several layers. The layout is then checked to ensure that it meets all of the design requirements, particularly timing requirements. The result is a set of design files known as an intermediate form that describes the layout. The design files are then converted into pattern generator files that are used to produce patterns called masks by an optical or electron beam pattern generator. During fabrication, these masks are used to pattern a silicon wafer using a sequence of photolithographic steps. The process of converting the specifications of an electrical circuit into a layout is called the physical design.
Cell placement in semiconductor fabrication involves a determination of where particular cells should optimally (or near-optimally) be located on the surface of an integrated circuit device. Due to the large number of components and the details required by the fabrication process for very large scale integrated (VLSI) devices, physical design is not practical without the aid of computers. As a result, most phases of physical design extensively use computer-aided design (CAD) tools, and many phases have already been partially or fully automated. Automation of the physical design process has increased the level of integration, reduced turn around time and enhanced chip performance. Several different programming languages have been created for electronic design automation (EDA) including Verilog, VHDL and TDML. A typical EDA system receives one or more high level behavioral descriptions of an IC device, and translates this high level design language description into netlists of various levels of abstraction.
Physical synthesis is prominent in the automated design of integrated circuits such as high performance processors and application-specific integrated circuits (ASICs). Physical synthesis is the process of concurrently optimizing placement, timing, power consumption, crosstalk effects and the like in an integrated circuit design. This comprehensive approach helps to eliminate iterations between circuit analysis and place-and-route. Physical synthesis has the ability to repower gates (changing their sizes), insert repeaters (buffers or inverters), clone gates or other combinational logic, etc., so the area of logic in the design remains fluid. However, physical synthesis can take days to complete, and the computational requirements are increasing as designs are ever larger and more gates need to be placed.
FIG. 1 illustrates a simplified example of conventional physical synthesis. The ////process begins with an input netlist created by an EDA tool (1). Logic cells in the netlist are placed in the available region of the IC using one or more placement tools, for example, a quadratic optimizer based on total wirelength (2). The logic cells first undergo global placement during which any non-overlap constraint among the cells is relaxed. The output of global placement accordingly contains overlaps among the cells that need to be resolved. The process of taking a global placement solution and resolving overlaps among the cells to create a “legal” (overlap-free) placement is known as legalization. After legalization, detailed placement is used to further optimize the placement objective by performing local movement of the cells. The legality of the placement is usually preserved during this stage of physical synthesis.
Once an initial placement is obtained the timing optimization stage performs various transforms such as buffer insertion, gate sizing, logic re-structuring, etc. to improve the timing characteristics of the design (3). Buffer insertion essentially adds cells to the existing design to introduce known delays. Gate sizing can increase the size of certain cells in the design. In some cases logic re-structuring transforms can also increase the number of cells in the design. In order to improve their efficiency, these transforms typically do not check for placement legality during the timing optimization stage. All of these transforms can thus potentially cause overlaps among the cells that again need to be resolved, so a check is made to see whether the layout is legal (4) and if not the legalization algorithm is employed (5). After timing optimization and any legalization, the process may use various constraints or design parameters to determine whether further placement and optimization are desired (6). If so, the process repeats iteratively at the placement step 2. After all placements and optimizations are complete, routing is provided for the circuit (7).
Legalization is thus employed at various stages in the design of an integrated circuit. During both of the stages described above, one of the key objectives of legalization is to minimize the perturbation of the cells from their original locations prior to the legalization step. During placement, this requirement preserves the characteristics of the input global placement solution. After timing optimization, if the cells are moved by a large distance during legalization then it can significantly degrade the performance of the circuit. In the past, legalization with minimal perturbation was fairly easy to achieve since designs had very few fixed modules or placement blockages and so presented a contiguous placement region with lots of empty space for cell movement. Such designs greatly simplified the legalization problem and most legalizers have been built to work with such designs. However, as VLSI circuits have become more complicated and denser, there has been a steady increase in the presence of various fixed modules or reserved spaces such as power grids, clock components, planned buses or datapaths, hierarchical logic, memory, analog blocks, or propriety (IP) blocks. Designers often pre-place these modules before running a physical synthesis flow. Hence, these macro blocks appear as placement blockages to the physical synthesis tool. In addition, designers are increasingly adopting a hierarchical design flow wherein individual macros or components of the design are synthesized separately and then integrated at the top level of the entire integrated circuit. At the top level these individual macros again appear as fixed modules or placement blockages.
As a result, designs today often contain numerous blockages and millions of movable modules. These fixed modules present a highly fragmented placement region in which the movable modules need to be placed, greatly complicating the legalization problem. Fractured designs greatly degrade the performance of traditional bin-based legalizers such as diffusion, network flow, recursive partitioning, constrained optimization, and slide-and-spiral legalizers. These tools construct a regular bin grid over the entire placement region and perform legalization by moving modules among these bins to satisfy capacity constraints, so they cannot effectively model designs with fragmented spaces. A fragmented placement region not only reduces the efficiency of these techniques but can also result in large perturbation of the modules during legalization leading to significant timing degradation, particularly the worst slack. Moreover, satisfying bin capacity does not by itself guarantee a legalized placement. There may be sufficient capacity in terms of overall available area within a bin but the bin has been broken up by blockages into non-contiguous areas which may be too small to contain a discrete module.
One way to overcome these drawbacks is to increase the number of bins in the regular bin grid, but such a change would cause a significant increase in the runtime of the legalization algorithm. Furthermore this modification still does not ensure that the modules would be moved with minimum perturbation from their original locations. It would, therefore, be desirable to devise an improved method of legalizing a placement which could take into consideration the presence of blockages in the placement region. It would be further advantageous if the method could reduce or minimize perturbation of the movable modules.